/* 
 * Single Number II
 * Given an array of integers, every element appears three times except for one.Find that single one
 */

#include "../../func.h"

int singleNumber1(vector<int> &nums)
{
    const int w = sizeof(int) * 8;
    int count[w];
    fill_n(&count[0], w, 0);

    for (int i = 0; i < nums.size(); ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            count[j] += (nums[i] >> j) & 1;
            count[j] %= 3;
        }
    }
    int result = 0;
    for (int i = 0; i < w; ++i)
    {
        result += (count[i] << i);
    }
    return result;
}

int singleNumber2(vector<int> &nums)
{
    int one = 0, two = 0, three = 0;
    for (auto i : nums)
    {
        two |= (one & i);
        one ^= i;
        three = ~(one & two);
        one &= three;
        two &= three;
    }
    return one;
}